/**
 * https://leetcode.cn/problems/house-robber-iv/
 * 2560.打家劫舍IV
 * 中等 欧琳琳 2024.11.20
 * 数组 二分查找
 */

class Solution {
public:
    bool canStealWithCapability(vector<int>& nums, int k, int capability) {
        int count = 0;
        int lastStolenIndex = -2;  // last stolen house's index
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] <= capability && (i - lastStolenIndex > 1)) {
                count++;
                lastStolenIndex = i;
                if (count >= k) {
                    return true;  // Successfully steal at least k houses
                }
            }
        }
        return false;
    }
    
    int minCapability(vector<int>& nums, int k) {
        int low = *min_element(nums.begin(), nums.end());
        int high = *max_element(nums.begin(), nums.end());
        int result = high;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canStealWithCapability(nums, k, mid)) {
                result = mid;  // This capability works, try for a smaller one
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        
        return result;
    }
};